'''
https://leetcode.cn/problems/closest-subsequence-sum/description/
'''
from typing import List

class Solution:
    def minAbsDifference(self, nums: List[int], goal: int) -> int:
        n = len(nums)
        def f(i, size, cur_weight, ans):
            if i == size:
                ans.append(cur_weight)
                return
            f(i + 1, size, cur_weight, ans)
            f(i + 1, size, cur_weight + nums[i], ans)

        left_ans = []
        right_ans = []
        f(0, n // 2, 0, left_ans)
        f(n // 2, n, 0, right_ans)
        left_ans.sort()
        right_ans.sort()
        ans = abs(goal)
        l, r = 0, len(right_ans) - 1
        while l < len(left_ans):
            while r > 0 and abs(right_ans[r - 1] + left_ans[l] - goal) <= abs(right_ans[r] + left_ans[l] - goal):
                r -= 1
            ans = min(ans, abs(right_ans[r] + left_ans[l] - goal))
            l += 1
        return ans

nums =[5,-7,3,5]
goal = 6
print(Solution().minAbsDifference(nums, goal))